{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Kth Largest Element in an Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #divide-and-conquer #quickselect #sorting #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #分治 #快速选择 #排序 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findKthLargest"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #数组中的第K个最大元素"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定整数数组 <code>nums</code> 和整数 <code>k</code>，请返回数组中第 <code><strong>k</strong></code> 个最大的元素。</p>\n",
    "\n",
    "<p>请注意，你需要找的是数组排序后的第 <code>k</code> 个最大的元素，而不是第 <code>k</code> 个不同的元素。</p>\n",
    "\n",
    "<p>你必须设计并实现时间复杂度为 <code>O(n)</code> 的算法解决此问题。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> <code>[3,2,1,5,6,4],</code> k = 2\n",
    "<strong>输出:</strong> 5\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> <code>[3,2,3,1,2,4,5,5,6], </code>k = 4\n",
    "<strong>输出:</strong> 4</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示： </strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= k &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>-10<sup>4</sup>&nbsp;&lt;= nums[i] &lt;= 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [kth-largest-element-in-an-array](https://leetcode.cn/problems/kth-largest-element-in-an-array/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [kth-largest-element-in-an-array](https://leetcode.cn/problems/kth-largest-element-in-an-array/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,2,1,5,6,4]\\n2', '[3,2,3,1,2,4,5,5,6]\\n4']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        return nums[-k]\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums, k):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        import heapq as pq\n",
    "        pq.heapify(nums)\n",
    "        for i in range(len(nums) - k):\n",
    "            pq.heappop(nums)\n",
    "        return pq.heappop(nums)\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums, k):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        nums.sort(reverse=True)\n",
    "        res,count=nums[0],1\n",
    "        \n",
    "        for i in range(1,len(nums)):\n",
    "            if count==k:\n",
    "                return res\n",
    "            else:\n",
    "                count+=1\n",
    "                res=nums[i]\n",
    "                \n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums, k):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if len(nums)<=0:\n",
    "            return 0\n",
    "        nums=sorted(nums)\n",
    "        return nums[-k]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        nums = self.fast(nums)\n",
    "        return(nums[-k])\n",
    "        \n",
    "        \n",
    "    def fast(self,nums):    \n",
    "        if len(nums) >= 2:\n",
    "            mid = nums[len(nums)//2]\n",
    "            left,right = [],[]\n",
    "            nums.remove(mid)\n",
    "            for i in nums:\n",
    "                if i<=mid:\n",
    "                    left.append(i)\n",
    "                else:\n",
    "                    right.append(i)\n",
    "            return self.fast(left) + [mid] + self.fast(right)\n",
    "        else:\n",
    "            return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, inputs, k):\n",
    "        class minHeap:\n",
    "            def __init__(self):\n",
    "                self.data = []\n",
    "                self.length = len(self.data)\n",
    "\n",
    "            def push(self, item):\n",
    "                self.data.append(item)\n",
    "                self.length += 1\n",
    "                self._siftdown(0, self.length - 1)\n",
    "\n",
    "            def _siftdown(self, startpos, pos):\n",
    "                #start=0, pos = len - 1\n",
    "                newitem = self.data[pos]\n",
    "                while pos > startpos:\n",
    "                    parentpos = (pos - 1) // 2\n",
    "                    parent = self.data[parentpos]\n",
    "                    if newitem < parent:\n",
    "                        self.data[pos] = parent\n",
    "                        pos = parentpos\n",
    "                        continue\n",
    "                    break\n",
    "                self.data[pos] = newitem\n",
    "\n",
    "            def pop(self):\n",
    "                if self.length > 0:\n",
    "                    res = self.data[0]\n",
    "                    self.data[0] = self.data[self.length - 1]\n",
    "                    self.data.pop()\n",
    "                    self.length -= 1\n",
    "                    self._siftup(0)\n",
    "                    return res\n",
    "\n",
    "            def _siftup(self, pos):\n",
    "                endpos = self.length\n",
    "                startpos = pos\n",
    "                newitem = self.data[pos]\n",
    "                childpos = 2 * pos + 1 #leftchild\n",
    "                while childpos < endpos:\n",
    "                    rightpos = childpos + 1\n",
    "                    if rightpos < endpos and not self.data[childpos] < self.data[rightpos]:\n",
    "                        childpos = rightpos\n",
    "                    self.data[pos] = self.data[childpos]\n",
    "                    pos = childpos\n",
    "                    childpos = 2 * pos + 1\n",
    "                # The leaf at pos is empty now.  Put newitem there, and bubble it up\n",
    "                # to its final resting place (by sifting its parents down).\n",
    "                self.data[pos] = newitem\n",
    "                self._siftdown(startpos, pos)\n",
    "        test = minHeap()\n",
    "        for i in range(k):\n",
    "            test.push(inputs[i])\n",
    "        for j in range(k, len(inputs)):\n",
    "            test.push(inputs[j])\n",
    "            print(test.pop())\n",
    "        print(test.data)\n",
    "        return test.data[0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums, k):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        maxx = max(nums)\n",
    "        minx = min(nums)\n",
    "        if maxx==minx:\n",
    "            return nums[k-1]\n",
    "        temp = maxx-minx\n",
    "        d = {}\n",
    "        for i in range(len(nums)):\n",
    "            n = maxx-nums[i]\n",
    "            if n < temp:\n",
    "                temp = n\n",
    "            d[i] = n\n",
    "        res = sorted(d.items(),key=lambda k:k[1])[k-1][0]\n",
    "        return nums[res]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums, k):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # nums.sort()\n",
    "        # return nums[-k]        \n",
    "        import random\n",
    "        def partition(nums, left, right):\n",
    "            p = random.randint(left, right)\n",
    "            nums[p], nums[right] = nums[right], nums[p]\n",
    "            i = left - 1\n",
    "            for j in range(left, right):\n",
    "                if nums[j] <= nums[right]:\n",
    "                    i += 1\n",
    "                    nums[i], nums[j] = nums[j], nums[i]\n",
    "            nums[i+1], nums[right] = nums[right], nums[i+1]            \n",
    "            return i+1\n",
    "        \n",
    "        def select(nums, left, right, k):\n",
    "            if left == right:\n",
    "                # return nums[left]\n",
    "                return left\n",
    "            p = partition(nums, left, right)\n",
    "            pos =  len(nums) - p\n",
    "            if pos == k:\n",
    "                # return nums[p]\n",
    "                return p\n",
    "            elif pos > k:\n",
    "                return select(nums, p+1, right, k)\n",
    "            else:\n",
    "                return select(nums, left, p-1, k)\n",
    "            \n",
    "        def search(nums,k):\n",
    "            l = len(nums)\n",
    "            nrow = l // 5\n",
    "            g =[]\n",
    "            for i in range(nrow):\n",
    "                g.append(sorted(nums[5*i:5*i+5]))\n",
    "            if l % 5:\n",
    "                nrow += 1\n",
    "                g.append(sorted(nums[-(l%5):]))\n",
    "            mid_line = [row[len(row)//2] for row in g]\n",
    "            p = select(mid_line, 0, len(mid_line)-1, len(mid_line)//2+1)\n",
    "            nums[p], nums[-1] = nums[-1], nums[p]\n",
    "            pos_i = 0\n",
    "            for j in range(l):\n",
    "                if nums[j] < nums[-1]:\n",
    "                    nums[pos_i], nums[j] = nums[j], nums[pos_i]\n",
    "                    pos_i += 1\n",
    "            nums[pos_i], nums[-1] = nums[-1], nums[pos_i]\n",
    "            pth = l - pos_i\n",
    "            if pth == k:\n",
    "                return nums[pos_i]\n",
    "            elif pth > k:\n",
    "                return search(nums[pos_i+1:], k)\n",
    "            else:\n",
    "                return search(nums[:pos_i], k - pth)\n",
    "            \n",
    "        return search(nums,k)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: 'List[int]', k: 'int') -> 'int':\n",
    "        from queue import PriorityQueue\n",
    "\n",
    "        pq = PriorityQueue()\n",
    "        for num in nums:\n",
    "            pq.put((-num, num))\n",
    "        # pq.put((5 * -1, 'Python'))\n",
    "        # pq.put((4 * -1, 'C'))\n",
    "        # pq.put((3 * -1, 'Js'))\n",
    "        print(\"Inside PriorityQueue: \", pq.queue)  # 内部存储\n",
    "        i = 0\n",
    "        while not pq.empty():\n",
    "            \n",
    "            i += 1\n",
    "            if i == k:\n",
    "                return pq.get()[1]\n",
    "            else:\n",
    "                print(pq.get()[1])\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums, k):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n = len(nums)-1\n",
    "        index = self.quicksort(nums,0,n,k)\n",
    "        return nums[index]\n",
    "    \n",
    "    def quicksort(self,nums,left,right,k):\n",
    "        if(left>right):\n",
    "            return left\n",
    "        p = self.partition(nums,left,right)\n",
    "        if(p+1 == k):\n",
    "            return p\n",
    "        if(p+1 > k):\n",
    "            return self.quicksort(nums,left,p-1,k)\n",
    "        else : \n",
    "            return self.quicksort(nums,p+1,right,k)\n",
    "            \n",
    "    def partition(self,nums,left,right):\n",
    "        mid = nums[left]\n",
    "        i = left+1\n",
    "        j = left\n",
    "        while(i<=right):\n",
    "            if(nums[i]>=mid):\n",
    "                nums[j+1],nums[i]=nums[i],nums[j+1]\n",
    "                j += 1\n",
    "            i += 1\n",
    "        nums[j],nums[left] = nums[left],nums[j]\n",
    "        return j\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     # 采用快速排序方法，分成的数列左边大于右边\n",
    "#     def findKthLargest(self, nums, k):\n",
    "#         n = len(nums)\n",
    "#         if (k > n):\n",
    "#             return\n",
    "#         index = self.quickSort(nums, 0, n-1, k)\n",
    "#         print(nums)\n",
    "#         return nums[index]\n",
    "        \n",
    "        \n",
    "#     def quickSort(self, nums, l, r, k):\n",
    "#         if l >= r:\n",
    "#             return l\n",
    "#         p = self.partition(nums, l, r)\n",
    "#         if p + 1 == k:\n",
    "#             return p\n",
    "#         if p + 1 > k:\n",
    "#             return self.quickSort(nums, l, p -1, k)\n",
    "#         else:\n",
    "#             return self.quickSort(nums, p + 1, r, k)\n",
    "\n",
    "\n",
    "#     def partition(self, nums, l, r):\n",
    "#         v = nums[l]\n",
    "#         j = l\n",
    "#         i = l + 1\n",
    "#         while i <= r:\n",
    "#             if nums[i] >= v:\n",
    "#                 nums[j+1],nums[i] = nums[i],nums[j+1]\n",
    "#                 j += 1\n",
    "#             i += 1\n",
    "#         nums[l], nums[j] = nums[j], nums[l]\n",
    "#         return j\n",
    "\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums, k):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        return self.quick_select(nums, 0, len(nums)-1, k)\n",
    "    \n",
    "    def quick_select(self, nums, left, right, k):\n",
    "        index = self.partition(nums, left, right)\n",
    "        if index == k-1:\n",
    "            return nums[index]\n",
    "        if index < k-1:\n",
    "            return self.quick_select(nums, index+1, right, k)\n",
    "        else:\n",
    "            return self.quick_select(nums, left, index-1, k)\n",
    "        \n",
    "    \n",
    "    def partition(self, nums, left, right):\n",
    "        tmp = nums[left]\n",
    "        while left < right:\n",
    "            while left < right and tmp >= nums[right]:\n",
    "                right -= 1\n",
    "            nums[left] = nums[right]\n",
    "            while left < right and tmp < nums[left]:\n",
    "                left += 1\n",
    "            nums[right] = nums[left]\n",
    "        nums[left] = tmp\n",
    "        return left\n",
    "    \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums, k):\n",
    "        return self.quickSelect(nums, 0, len(nums)-1, k)\n",
    "\n",
    "    def quickSelect(self, nums, start, n, k): # quick select\n",
    "        pos = self.partition(nums, start, n)\n",
    "        if pos == k-1:\n",
    "            return nums[pos]\n",
    "        elif pos >= k:\n",
    "            return self.quickSelect(nums, start, pos - 1, k)\n",
    "        return self.quickSelect(nums, pos + 1, n, k)\n",
    "\n",
    "    def partition(self, nums, left, right):\n",
    "        pivot = nums[right] # pick the last one as pivot\n",
    "        i = left\n",
    "        for j in range(left, right): # left to right -1\n",
    "            if nums[j] > pivot: # the larger elements are in left side\n",
    "                nums[j], nums[i] = nums[i], nums[j]\n",
    "                i += 1\n",
    "        nums[right], nums[i] = nums[i], nums[right] # swap the i and the last element\n",
    "        return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution(object):\n",
    "    def findKthLargest(self, nums, k):\n",
    "        min_heap = nums[:k]\n",
    "        heapq.heapify(min_heap)\n",
    "        for i in range(k, len(nums)):\n",
    "            if nums[i] > min_heap[0]:\n",
    "                heapq.heappop(min_heap)\n",
    "                heapq.heappush(min_heap, nums[i])\n",
    "        return min_heap[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        return self.quick_sort(nums, k)\n",
    "    \n",
    "    def quick_sort(self, nums, k):\n",
    "        k = len(nums) - k\n",
    "        left = 0\n",
    "        right = len(nums) - 1\n",
    "        while left < right:\n",
    "            j = self.partition(nums, left, right)\n",
    "            if j == k:\n",
    "                break\n",
    "            elif j < k:\n",
    "                left = j + 1\n",
    "            else:\n",
    "                right = j - 1\n",
    "        return nums[k]\n",
    "    \n",
    "    def partition(self, nums, left, right):\n",
    "        while True:\n",
    "            while nums[left] < nums[right]:\n",
    "                right -= 1\n",
    "            else:\n",
    "                nums[left], nums[right] = nums[right], nums[left]\n",
    "                if left >= right:\n",
    "                    break\n",
    "                left += 1\n",
    "            \n",
    "            while nums[left] < nums[right]:\n",
    "                left += 1\n",
    "            else:\n",
    "                nums[left], nums[right] = nums[right], nums[left]\n",
    "                if left >= right:\n",
    "                    break\n",
    "                right -= 1\n",
    "            \n",
    "        return left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        nums = sorted(nums, reverse=True)\n",
    "        return nums[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        k=len(nums)-k \n",
    "        left,right=0,len(nums)\n",
    "        def partion(nums,start,end):\n",
    "            left,right=start,end\n",
    "            pivot=nums[start]\n",
    "            while True:\n",
    "                while left+1<end and nums[left+1]<=pivot:\n",
    "                    left+=1\n",
    "                while right-1>start and nums[right-1]>pivot:\n",
    "                    right-=1\n",
    "                if left+1>=right:\n",
    "                    nums[start],nums[left]=nums[left],nums[start]\n",
    "                    return left\n",
    "                nums[left+1],nums[right-1]=nums[right-1],nums[left+1]        \n",
    "\n",
    "        \n",
    "        while left<right:\n",
    "            t=partion(nums,left,right)\n",
    "            if t>k:\n",
    "                right=t \n",
    "            elif t<k:\n",
    "                left=t+1\n",
    "            else: return nums[k]\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        # build a heap\n",
    "        for i in range(k // 2, -1, -1):\n",
    "            self.buildHeap(nums, i, k)\n",
    "\n",
    "        # adjust the heap\n",
    "        for j in range(k, len(nums)):\n",
    "            if nums[j] > nums[0]:\n",
    "                nums[j], nums[0] = nums[0], nums[j]\n",
    "                self.buildHeap(nums, 0, k)\n",
    "        return nums[0]\n",
    "\n",
    "\n",
    "    def buildHeap(self, nums, start, end):\n",
    "        left = start * 2 + 1\n",
    "        right = left + 1\n",
    "        min_pos = start\n",
    "        if left < end and nums[left] < nums[start]:\n",
    "            min_pos = left\n",
    "        if right < end and nums[right] < nums[min_pos]:\n",
    "            min_pos = right\n",
    "        if min_pos != start:\n",
    "            nums[start], nums[min_pos] = nums[min_pos], nums[start] # 升起来\n",
    "            self.buildHeap(nums, min_pos, end)  # 沉下去"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        for _ in range(k):\n",
    "            tmp = float('-inf')\n",
    "            for num in nums:\n",
    "                tmp = num if tmp < num else tmp\n",
    "            nums.remove(tmp)\n",
    "        return tmp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        heapq.heapify(nums)\n",
    "        res = []\n",
    "        while len(nums) != 0:\n",
    "            res.append(heappop(nums))\n",
    "        return res[-k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        return nums[k-1]\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        # 返回排序后数组第k大的数 = 第n-k小的数字\n",
    "        # 快排、堆排都可以做\n",
    "        # 选择中间的数字，执行一次快排，如果位置==k - 1，那么返回它,如果位置<k - 1，那么往右边排序，反之往左边排序\n",
    "        tar = len(nums) - k\n",
    "        def qsort(lo, hi):\n",
    "            if lo >= hi:\n",
    "                return nums[lo]\n",
    "            x = nums[(lo + hi) >> 1]\n",
    "            i, j = lo - 1, hi + 1\n",
    "            while i < j:\n",
    "                i += 1\n",
    "                while nums[i] < x: i += 1\n",
    "                j -= 1\n",
    "                while nums[j] > x: j -= 1\n",
    "                if i < j:\n",
    "                    nums[i], nums[j] = nums[j], nums[i]\n",
    "            if j < tar:\n",
    "                return qsort(j + 1, hi)\n",
    "            else:\n",
    "                return qsort(lo, j)\n",
    "            \n",
    "        return qsort(0, len(nums) - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        # 最大堆\n",
    "        ans = []\n",
    "        for i in range(len(nums)):  # 依次取出最大堆的堆顶元素(即当前列表的最大值)\n",
    "            nums_tmp = [i*(-1) for i in nums]  # 将列表中的所有元素均乘以-1\n",
    "            heapq.heapify(nums_tmp)  # 利用变换后的列表创建最小堆\n",
    "            nums = [i*(-1) for i in nums_tmp]  # 将最小堆对应列表中的所有元素均乘以-1\n",
    "            heap_peak = heapq.heappop(nums)  # 取出堆顶元素\n",
    "            ans.append(heap_peak)\n",
    "        return ans[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import queue\n",
    "class Node(object):\n",
    "    def __init__(self,x):\n",
    "        self.x=x\n",
    "    def __lt__(self,other):\n",
    "        return self.x>other.x\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        import queue\n",
    "        q=queue.PriorityQueue()\n",
    "        for num in nums:\n",
    "            tmp=Node(num)\n",
    "            q.put(tmp)\n",
    "        for _ in range(k):\n",
    "            ans=q.get()\n",
    "        return ans.x\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        target = nums[0]\n",
    "        start, end = 0, len(nums) - 1 \n",
    "        while start <= end:\n",
    "            while start <= end and nums[start] < target:\n",
    "                nums[start], nums[end] = nums[end], nums[start]\n",
    "                end -= 1\n",
    "            start += 1\n",
    "\n",
    "        nums[end], nums[0] = nums[0], nums[end]\n",
    "        if end == k - 1:\n",
    "            return nums[end]\n",
    "        elif end > k - 1:\n",
    "            return self.findKthLargest(nums[:end], k)\n",
    "        else:\n",
    "            return self.findKthLargest(nums[end + 1:], k - end - 1)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, nums, i, j):\n",
    "        pivot = nums[i]\n",
    "        while i < j:\n",
    "            while nums[j]<=pivot and i<j:\n",
    "                j -= 1\n",
    "            nums[i] = nums[j]\n",
    "            while nums[i]>=pivot and i<j:\n",
    "                i += 1\n",
    "            nums[j] = nums[i]\n",
    "        nums[i] = pivot\n",
    "        return i\n",
    "\n",
    "    def findK(self, nums, i, j, k):\n",
    "        kk = self.partition(nums, i, j)\n",
    "        if kk == k-1: \n",
    "            return nums[kk]\n",
    "        elif kk < k:\n",
    "            return self.findK(nums, kk+1, j, k)\n",
    "        else:\n",
    "            return self.findK(nums, i, kk-1, k)\n",
    "\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        i, j = 0, len(nums)-1\n",
    "        tmp = nums[i]\n",
    "        nums[i] = nums[(i+j)//2]\n",
    "        nums[(i+j)//2] = tmp\n",
    "        return self.findK(nums, i, j, k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, arr: List[int], k: int) -> int:\n",
    "        def swap(arr, i, j):\n",
    "            arr[i], arr[j] = arr[j], arr[i]\n",
    "\n",
    "\n",
    "        def randompivot(arr):\n",
    "            pivot = int(random.uniform(0, len(arr)))\n",
    "            swap(arr, 0, pivot)\n",
    "\n",
    "\n",
    "        def partition(arr, left, right):\n",
    "\n",
    "            pivot = arr[left]  # int(random.random()*n)\n",
    "            l, r = left, right\n",
    "            while l < r:\n",
    "                while l < r and arr[r] >= pivot:\n",
    "                    r -= 1\n",
    "                arr[l] = arr[r]\n",
    "                while l < r and arr[l] <= pivot:\n",
    "                    l += 1\n",
    "                arr[r] = arr[l]\n",
    "            arr[l] = pivot\n",
    "            return l\n",
    "\n",
    "\n",
    "        def quicksort(arr, left, right):\n",
    "            # print(left,right)\n",
    "            if left >= right:\n",
    "                return\n",
    "            mid = partition(arr, left, right)\n",
    "            quicksort(arr, left, mid-1)\n",
    "            quicksort(arr, mid+1, right)\n",
    "\n",
    "\n",
    "        def topk(arr, left, right, k):\n",
    "            mid = partition(arr, left, right)\n",
    "            if mid == k-1:\n",
    "                return arr[mid]\n",
    "            if mid < k-1:\n",
    "                return topk(arr, mid+1, right, k)\n",
    "            else:\n",
    "                return topk(arr, left, mid-1, k)\n",
    "        \n",
    "        n = len(arr)\n",
    "        randompivot(arr)\n",
    "        # quicksort(arr, 0, n-1)\n",
    "        return topk(arr, 0, n-1, n+1-k)\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        return self.quickSelect(nums, 0, n - 1, n - k)\n",
    "    \n",
    "    def quickSelect(self, nums, left, right, idx):\n",
    "        pivot = self.partition(nums, left, right)\n",
    "        if pivot < idx:\n",
    "            return self.quickSelect(nums, left + 1, right, idx)\n",
    "        elif pivot > idx:\n",
    "            return self.quickSelect(nums, left, right - 1, idx)\n",
    "        else:\n",
    "            return nums[pivot]\n",
    "    \n",
    "    def partition(self, nums, left, right):\n",
    "        idx = random.randrange(left, right + 1)\n",
    "        nums[left], nums[idx] = nums[idx], nums[left]\n",
    "        pivot = left\n",
    "        for i in range(left + 1, right + 1):\n",
    "            if nums[i] < nums[left]:\n",
    "                pivot += 1\n",
    "                nums[i], nums[pivot] = nums[pivot], nums[i]\n",
    "        if pivot != left:\n",
    "            nums[left], nums[pivot] = nums[pivot], nums[left]\n",
    "        return pivot"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, arr: List[int], k: int) -> int:\n",
    "        def swap(arr, i, j):\n",
    "            arr[i], arr[j] = arr[j], arr[i]\n",
    "\n",
    "\n",
    "        def randompivot(arr):\n",
    "            pivot = random.randint(0, len(arr)-1) \n",
    "            swap(arr, 0, pivot)\n",
    "\n",
    "\n",
    "        def partition(arr, left, right):\n",
    "\n",
    "            pivot = arr[left]  # int(random.random()*n)\n",
    "            l, r = left, right\n",
    "            while l < r:\n",
    "                while l < r and arr[r] >= pivot:\n",
    "                    r -= 1\n",
    "                arr[l] = arr[r]\n",
    "                while l < r and arr[l] <= pivot:\n",
    "                    l += 1\n",
    "                arr[r] = arr[l]\n",
    "            arr[l] = pivot\n",
    "            return l\n",
    "\n",
    "\n",
    "        # def quicksort(arr, left, right):\n",
    "        #     # print(left,right)\n",
    "        #     if left >= right:\n",
    "        #         return\n",
    "        #     mid = partition(arr, left, right)\n",
    "        #     quicksort(arr, left, mid-1)\n",
    "        #     quicksort(arr, mid+1, right)\n",
    "\n",
    "\n",
    "        def topk(arr, left, right, k):\n",
    "            mid = partition(arr, left, right)\n",
    "            if mid == k-1:\n",
    "                return arr[mid]\n",
    "            if mid < k-1:\n",
    "                return topk(arr, mid+1, right, k)\n",
    "            else:\n",
    "                return topk(arr, left, mid-1, k)\n",
    "        \n",
    "        n = len(arr)\n",
    "        randompivot(arr)\n",
    "        # quicksort(arr, 0, n-1)\n",
    "        return topk(arr, 0, n-1, n+1-k)\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        \n",
    "        def partition_once(nums, low, high):\n",
    "            pi = low\n",
    "            li = low + 1\n",
    "            ri = high\n",
    "            while ri >= li:\n",
    "                if nums[li] > nums[pi]:\n",
    "                    flag = nums[ri]\n",
    "                    nums[ri] = nums[li]\n",
    "                    nums[li] = flag\n",
    "                    ri -= 1\n",
    "                else:\n",
    "                    li += 1\n",
    "            pi = li-1\n",
    "            flag = nums[low]\n",
    "            nums[low] = nums[pi]\n",
    "            nums[pi] = flag\n",
    "            return pi\n",
    "        \n",
    "        def partition(nums, low, high):\n",
    "            if low > high:\n",
    "                return -1\n",
    "            p = partition_once(nums, low, high)\n",
    "            partition(nums, low, p-1)\n",
    "            partition(nums, p+1, high)\n",
    "            return\n",
    "        \n",
    "        partition(nums, 0, len(nums)-1)\n",
    "        return nums[len(nums)-k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        def partition(l, r):\n",
    "            pivot = random.randrange(l, r+1)\n",
    "            i, j = l, r\n",
    "            while i<j:\n",
    "                while i<j and nums[j]<=nums[l]:j-=1\n",
    "                while i<j and nums[i]>=nums[l]:i+=1\n",
    "                nums[i], nums[j] = nums[j], nums[i]\n",
    "            nums[l], nums[i] = nums[i], nums[l]\n",
    "            return i\n",
    "        \n",
    "        def quickscort(l, r):\n",
    "            if l>=r:return\n",
    "            i = partition(l, r)\n",
    "            if i==k:\n",
    "                return \n",
    "            elif i<k:\n",
    "                quickscort(i+1, r)\n",
    "            else:\n",
    "                quickscort(l, i-1)   \n",
    "        k = k-1\n",
    "        quickscort(0, len(nums)-1)\n",
    "        \n",
    "        return nums[k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        def partition(nums, left, right):\n",
    "            i, j = left, right\n",
    "            pivot = nums[i]\n",
    "            while i < j:\n",
    "                while i < j and pivot <= nums[j]:\n",
    "                    j -= 1\n",
    "                nums[i] = nums[j]\n",
    "                while i < j and nums[i] <= pivot:\n",
    "                    i += 1\n",
    "                nums[j] = nums[i]\n",
    "            nums[i] = pivot\n",
    "            return i\n",
    "\n",
    "\n",
    "\n",
    "        def topKPartition(nums, k, left, right):\n",
    "            if left < right:\n",
    "                index = partition(nums, left, right)\n",
    "                if index == k:\n",
    "                    return \n",
    "                elif index > k:\n",
    "                    topKPartition(nums, k, left, index-1)\n",
    "                else:\n",
    "                    topKPartition(nums, k, index+1, right)\n",
    "        \n",
    "        if not nums or k < 0:\n",
    "            return\n",
    "        n = len(nums)\n",
    "        topKPartition(nums, n-k, 0, n-1)\n",
    "        return nums[n-k]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        # 快速选择\n",
    "        return self.quick_sort(nums, 0, len(nums)-1, k)\n",
    "\n",
    "    def quick_sort(self, nums, left, right, k):\n",
    "        if right <= left: return nums[left]\n",
    "        low, high = left, right\n",
    "        mid_value = nums[low]\n",
    "        while low < high:\n",
    "            while low < high and nums[high] <= mid_value: high -= 1\n",
    "            nums[low] = nums[high]\n",
    "            while low < high and nums[low] > mid_value: low += 1\n",
    "            nums[high] = nums[low]\n",
    "        nums[low] = mid_value\n",
    "        cnt = low - left + 1\n",
    "        if k == cnt: return nums[low]\n",
    "        elif k < cnt: return self.quick_sort(nums, left, low-1, k)\n",
    "        else: return self.quick_sort(nums, low+1, right, k-cnt)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        import heapq\n",
    "        n=len(nums)\n",
    "        heapq.heapify(nums)\n",
    "        lis=[]\n",
    "        for i in range(n):\n",
    "            lis.append(heapq.heappop(nums))\n",
    "        return lis[-k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        heapq.heapify(nums) # 建堆\n",
    "        ls = []\n",
    "        for i in range(len(nums)):\n",
    "            min_number = heapq.heappop(nums) # 每次弹出最小的数值\n",
    "            if ls == []:\n",
    "                ls.append(min_number)\n",
    "            else:\n",
    "                if min_number >= ls[-1]:\n",
    "                    ls.append(min_number)\n",
    "                else:\n",
    "                    continue\n",
    "        return ls[-k] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        import heapq\n",
    "        heapq.heapify(nums)\n",
    "        stb = [heapq.heappop(nums) for i in range(len(nums))]\n",
    "        return stb[len(nums) - k]        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        def maxHepify(arr, i, end):     # 大顶堆\n",
    "            j = 2*i + 1                 # j为i的左子节点【建堆时下标0表示堆顶】\n",
    "            while j <= end:             # 自上而下进行调整\n",
    "                if j+1 <= end and arr[j+1] > arr[j]:    # i的左右子节点分别为j和j+1\n",
    "                    j += 1                              # 取两者之间的较大者\n",
    "                \n",
    "                if arr[i] < arr[j]:             # 若i指示的元素小于其子节点中的较大者\n",
    "                    arr[i], arr[j] = arr[j], arr[i]     # 交换i和j的元素，并继续往下判断\n",
    "                    i = j                       # 往下走：i调整为其子节点j\n",
    "                    j = 2*i + 1                 # j调整为i的左子节点\n",
    "                else:                           # 否则，结束调整\n",
    "                    break\n",
    "        \n",
    "        n = len(nums)\n",
    "        \n",
    "        # 建堆【大顶堆】\n",
    "        for i in range(n//2-1, -1, -1):\n",
    "            maxHepify(nums, i, n-1)\n",
    "\n",
    "        # 排序：依次将堆顶元素（当前最大值）放置到尾部，并调整堆\n",
    "        # k-1次重建堆（堆顶元素），或 k次交换到尾部（倒数第k个元素）\n",
    "        for j in range(n-1, n-k-1, -1):\n",
    "            nums[0], nums[j] = nums[j], nums[0]     # 堆顶元素（当前最大值）放置到尾部j\n",
    "            maxHepify(nums, 0, j-1)                 # j-1变成尾部，并从堆顶0开始调整堆\n",
    "        \n",
    "        return nums[-k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        import heapq\n",
    "        heapq.heapify(nums)\n",
    "        sorted_nums = []\n",
    "        while nums:\n",
    "            sorted_nums.append(heapq.heappop(nums))\n",
    "        return sorted_nums[-k]\n",
    "\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        import heapq\n",
    "        \n",
    "        heapq.heapify(nums)\n",
    "        res = [heapq.heappop(nums) for i in range(len(nums))]\n",
    "        return res[-k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        split=nums.pop()\n",
    "        left=[] # v for v in nums if v<=split\n",
    "        right=[] # v for v in nums if v>split\n",
    "        split_count=1\n",
    "        while len(nums)>0:\n",
    "            v=nums.pop()\n",
    "            if v>split:\n",
    "                right.append(v)\n",
    "                split_count+=1\n",
    "            else:\n",
    "                left.append(v)\n",
    "        if split_count==k:\n",
    "            return split\n",
    "        elif split_count<k:\n",
    "            #  find result in left\n",
    "            return self.findKthLargest(left, k-split_count)\n",
    "        else:\n",
    "            #  find result in right\n",
    "            return self.findKthLargest(right, k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def heapify(self, _nums):\n",
    "        last_non_leaf = (len(_nums) - 2) // 2\n",
    "        \n",
    "        for i in range(last_non_leaf, -1, -1):\n",
    "            self.heap_down(_nums, i)\n",
    "    \n",
    "    def heap_down(self, _nums, i):\n",
    "        left_child = 2 * i + 1\n",
    "        right_child = 2 * i + 2\n",
    "        larger = i\n",
    "        \n",
    "        if left_child < len(_nums) and _nums[left_child] > _nums[larger]:\n",
    "            larger = left_child\n",
    "        \n",
    "        if right_child < len(_nums) and _nums[right_child] > _nums[larger]:\n",
    "            larger = right_child\n",
    "        \n",
    "        if larger != i:\n",
    "            _nums[i], _nums[larger] = _nums[larger], _nums[i]\n",
    "            self.heap_down(_nums, larger)\n",
    "    \n",
    "    def extract_max(self, _nums):\n",
    "        if len(_nums) == 0:\n",
    "            return None\n",
    "        if len(_nums) == 1:\n",
    "            return _nums.pop()\n",
    "        \n",
    "        root = _nums[0]\n",
    "        _nums[0] = _nums.pop()\n",
    "        self.heap_down(_nums, 0)\n",
    "        \n",
    "        return root\n",
    "    \n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        self.heapify(nums)\n",
    "        result = 0\n",
    "        for i in range(k):\n",
    "            result = self.extract_max(nums)\n",
    "        \n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            nums[i] = -nums[i]\n",
    "        heapify(nums)\n",
    "        for i in range(k - 1):\n",
    "            heappop(nums)\n",
    "        return -heappop(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        p = 0\n",
    "        for i in range(k):\n",
    "            p = nums.pop()\n",
    "        return p"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        heapq.heapify(nums)\n",
    "\n",
    "        for i in range(len(nums)-k):\n",
    "            print(heapq.heappop(nums))\n",
    "        return heapq.heappop(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        heap = [-i for i in nums]\n",
    "        nums.clear()\n",
    "        heapify(heap)\n",
    "        for _ in range(k):\n",
    "            ans = heappop(heap)\n",
    "        return -ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        return sorted(nums)[-k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        #copy\n",
    "        def quick_select(nums,k):\n",
    "            pivot= random.choice(nums)\n",
    "            big,equal,small = [],[],[]\n",
    "            for num in nums:\n",
    "                if num>pivot:\n",
    "                    big.append(num)\n",
    "                elif num<pivot:\n",
    "                    small.append(num)\n",
    "                else:\n",
    "                    equal.append(num)\n",
    "            if k <= len(big):\n",
    "                return quick_select(big,k)\n",
    "            if len(nums)- len(small) <k:\n",
    "                return quick_select(small,k-len(nums)+len(small))\n",
    "            return pivot\n",
    "\n",
    "        return quick_select(nums,k)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        def quick_select(nums,k):\n",
    "            pivot = random.choice(nums)\n",
    "            big,equal,small = [],[],[]\n",
    "            for num in nums:\n",
    "                if num>pivot:\n",
    "                    big.append(num)\n",
    "                elif num<pivot:\n",
    "                    small.append(num)\n",
    "                else:\n",
    "                    equal.append(num)\n",
    "            if k <= len(big):\n",
    "                return quick_select(big,k)\n",
    "            if len(nums) - len(small) < k:\n",
    "                return quick_select(small,k-len(nums)+len(small))\n",
    "            return pivot\n",
    "        return quick_select(nums,k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        # nums.sort(reverse=True)\n",
    "        def quick_select(nums):\n",
    "            if len(nums)<2:\n",
    "                return nums\n",
    "            mid=random.choice(nums)\n",
    "            big,equal,small = [],[],[]\n",
    "            # nums.remove(mid)\n",
    "            for num in nums:\n",
    "                if num>mid:\n",
    "                    big.append(num)\n",
    "                elif num<mid:\n",
    "                    small.append(num)\n",
    "                else:\n",
    "                    equal.append(num)\n",
    "            return (quick_select(big)+equal+quick_select(small))\n",
    "        return quick_select(nums)[k-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        def quick_select(nums,k):\n",
    "            pivot= random.choice(nums)\n",
    "            big,equal,small = [],[],[]\n",
    "            for num in nums:\n",
    "                if num>pivot:\n",
    "                    big.append(num)\n",
    "                elif num<pivot:\n",
    "                    small.append(num)\n",
    "                else:\n",
    "                    equal.append(num)\n",
    "            if k <= len(big):\n",
    "                return quick_select(big,k)\n",
    "            if len(nums)- len(small) <k:\n",
    "                return quick_select(small,k-len(nums)+len(small))\n",
    "            return pivot\n",
    "\n",
    "        return quick_select(nums,k)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        # nums.sort(reverse=True)\n",
    "        def quick_select(nums):\n",
    "            if len(nums)<2:\n",
    "                return nums\n",
    "            mid=nums[len(nums)//2]\n",
    "            big,equal,small = [],[],[]\n",
    "            # nums.remove(mid)#很慢因为可能会会重复删除，增加时间复杂度\n",
    "            for num in nums:\n",
    "                if num>mid:\n",
    "                    big.append(num)\n",
    "                elif num<mid:\n",
    "                    small.append(num)\n",
    "                else:\n",
    "                    equal.append(num)\n",
    "            return (quick_select(big)+equal+quick_select(small))\n",
    "        return quick_select(nums)[k-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        return self.quickSelect(nums, 0, len(nums) - 1, len(nums) - k)\n",
    "    def quickSelect(self, nums, left, right, k):\n",
    "        pivot = self.partition(nums,left,right)\n",
    "        if k == pivot:\n",
    "            return nums[k]\n",
    "        if k > pivot:\n",
    "            return self.quickSelect(nums, pivot + 1, right, k)\n",
    "        if k < pivot:\n",
    "            return self.quickSelect(nums, left, pivot - 1, k)\n",
    "\n",
    "    def partition(self, nums, low, high):\n",
    "        pivot = nums[high]\n",
    "        left = low\n",
    "        right = high - 1\n",
    "\n",
    "        while left <= right:\n",
    "            while nums[left] < pivot and left <= right:\n",
    "                left += 1\n",
    "            while nums[right] > pivot and left <= right:\n",
    "                right -= 1\n",
    "            if left <= right:\n",
    "                nums[left],nums[right] = nums[right], nums[left]\n",
    "                left += 1\n",
    "                right -= 1\n",
    "        nums[left],nums[high] = nums[high], nums[left]\n",
    "        return left "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        n=len(nums)\n",
    "        def quicksort(nums,l,r,k):\n",
    "            if l>=r:\n",
    "                return nums[k]\n",
    "            pivot=nums[l]\n",
    "            i=l+1\n",
    "            j=r\n",
    "            while i<j:\n",
    "                while i<=r and nums[i]<pivot:\n",
    "                    i+=1\n",
    "                while  j>=l and nums[j]>pivot:\n",
    "                    j-=1\n",
    "                if i<j:\n",
    "                    tmp=nums[i]\n",
    "                    nums[i]=nums[j]\n",
    "                    nums[j]=tmp\n",
    "                    i+=1\n",
    "                    j-=1\n",
    "            if nums[j]<pivot:\n",
    "                nums[l]=nums[j]\n",
    "                nums[j]=pivot\n",
    "            if j==k:\n",
    "                return nums[k]\n",
    "            if k<=j:\n",
    "                return quicksort(nums,l,j-1,k)\n",
    "            else:\n",
    "                return quicksort(nums,j+1,r,k)\n",
    "        return quicksort(nums,0,n-1,n-k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        def quicl_select(nums,k):\n",
    "            sample_num = random.choice(nums)\n",
    "            big,small,equal = [],[],[]\n",
    "            for i in nums:\n",
    "                if i > sample_num:\n",
    "                    big.append(i)\n",
    "                elif i < sample_num:\n",
    "                    small.append(i)\n",
    "                else:\n",
    "                    equal.append(i)\n",
    "            if k <= len(big):\n",
    "                return quicl_select(big,k)\n",
    "            elif  len(nums) - len(small) < k:\n",
    "                return quicl_select(small,k - len(nums)+ len(small))\n",
    "            \n",
    "            return sample_num \n",
    "        return quicl_select(nums,k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        heapify(nums)\n",
    " \n",
    "        return nlargest(k, nums)[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import PriorityQueue\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        l = len(nums)\n",
    "        q = PriorityQueue()\n",
    "        for num in nums:\n",
    "            q.put([num, num])\n",
    "        while len(q.queue) > k:\n",
    "            c = q.get()\n",
    "            # print(c)\n",
    "        return q.get()[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        heap = [0] + nums \n",
    "        \n",
    "        def down(i):\n",
    "            t = i \n",
    "            if 2 * i <= n and heap[t] > heap[2 * i]:\n",
    "                t = 2 * i \n",
    "            if 2 * i + 1 <= n and heap[t] > heap[2 * i + 1]:\n",
    "                t = 2 * i + 1\n",
    "            if t != i:\n",
    "                heap[t], heap[i] = heap[i], heap[t]\n",
    "                down(t)\n",
    "        \n",
    "        for i in range(n // 2, 0, -1):\n",
    "            down(i)\n",
    "\n",
    "        for _ in range(n - k):\n",
    "            heap[1] = heap[n]\n",
    "            n -= 1\n",
    "            down(1)\n",
    "        return heap[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        from queue import PriorityQueue as PQ\n",
    "        q = PQ()\n",
    "        for num in nums:\n",
    "            q.put((-num, num))\n",
    "        \n",
    "        for i in range(k):\n",
    "            res = q.get()\n",
    "        return res[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        q=[]\n",
    "        for i in nums:\n",
    "            q.append((-i,i))\n",
    "        heapq.heapify(q)\n",
    "\n",
    "        for i in range(k):\n",
    "            res=heapq.heappop(q)\n",
    "        return res[1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import PriorityQueue\n",
    "\n",
    "class Cmp:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "    def __lt__(self, other):\n",
    "        return self.val < other.val\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        myque = PriorityQueue()\n",
    "        for num in nums:\n",
    "            myque.put(Cmp(num))\n",
    "            if myque.qsize() > k:\n",
    "                myque.get()\n",
    "        return myque.get().val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        # 数组长度\n",
    "        n = len(nums)\n",
    "        # 调整该元素作为顶点的堆\n",
    "        def maxHeapify(i, size):\n",
    "            # 孩子的索引\n",
    "            left = 2 * i + 1\n",
    "            right = 2 * i + 2\n",
    "            # 找出其孩子的最大值\n",
    "            max_index = i\n",
    "            max_ = nums[i]\n",
    "            if left < size and max_ < nums[left]:\n",
    "                max_ = nums[left]\n",
    "                max_index = left\n",
    "            if right < size and max_ < nums[right]:\n",
    "                max_ = nums[right]\n",
    "                max_index = right\n",
    "            if max_index == i:\n",
    "                return\n",
    "            # 交换元素\n",
    "            nums[i], nums[max_index] = nums[max_index], nums[i]\n",
    "            # 向下调整\n",
    "            maxHeapify(max_index, size)\n",
    "        # 建立大根堆\n",
    "        def build_heap():\n",
    "            for i in range(n-1, -1, -1):\n",
    "                maxHeapify(i, n)\n",
    "        build_heap()\n",
    "        for i in range(k-1):\n",
    "            nums[0], nums[n-i-1] = nums[n-i-1], nums[0]\n",
    "            maxHeapify(0, n-i-1)\n",
    "        return nums[0]\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        def swap(i,j):\n",
    "            nums[i], nums[j] = nums[j], nums[i]\n",
    "\n",
    "        def shift(l, r, nums):\n",
    "            min_idx = l\n",
    "            if 2*l + 1 <= r and nums[2*l+1] < nums[min_idx]:\n",
    "                min_idx = 2*l + 1\n",
    "            if 2*l + 2 <= r and nums[2*l+2] < nums[min_idx]:\n",
    "                min_idx = 2*l + 2\n",
    "            if min_idx != l:\n",
    "                swap(l, min_idx)\n",
    "                shift(min_idx, r, nums)\n",
    "\n",
    "        for i in range((k-1)//2, -1, -1):\n",
    "            shift(i, k-1, nums)\n",
    "\n",
    "        for i in range(k, len(nums)):\n",
    "            if nums[i] > nums[0]:\n",
    "                swap(0, i)\n",
    "                shift(0, k-1, nums)\n",
    "        \n",
    "        return nums[0]\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        def buildheap(n):\n",
    "            for i in range(n//2, -1, -1):\n",
    "                heapify(i, n)\n",
    "\n",
    "        def heapify(i, n):\n",
    "            left = 2 * i + 1\n",
    "            right = 2 * i + 2\n",
    "            largest = i\n",
    "            if left < n and nums[left] > nums[largest]:\n",
    "                largest = left\n",
    "            if right < n and nums[right] > nums[largest]:\n",
    "                largest = right\n",
    "            if largest != i:\n",
    "                nums[i], nums[largest] = nums[largest], nums[i]\n",
    "                heapify(largest, n)\n",
    "\n",
    "        \n",
    "        n = len(nums)\n",
    "        buildheap(n)\n",
    "        print(nums)\n",
    "        for i in range(n-1, n - k, -1):\n",
    "            nums[0], nums[i] = nums[i], nums[0]\n",
    "            heapify(0, i)\n",
    "\n",
    "        return nums[0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        \n",
    "        \n",
    "        def Qsort(start, end):\n",
    "            # print(start, end)\n",
    "            if start >= end:\n",
    "                return \n",
    "            # idx = random.randint(start, end)\n",
    "            # nums[start], nums[idx] = nums[idx], nums[start]\n",
    "            base = nums[start]\n",
    "            # print(base)\n",
    "            lt, i, gt = start + 1, start + 1, end\n",
    "\n",
    "            while i <= gt:\n",
    "                if nums[i] > base:\n",
    "                    nums[gt], nums[i] = nums[i], nums[gt]\n",
    "                    gt -= 1\n",
    "                elif nums[i] < base:\n",
    "                    nums[lt], nums[i] = nums[i], nums[lt]\n",
    "                    lt += 1\n",
    "                    i += 1\n",
    "                else:\n",
    "                    i += 1\n",
    "            nums[lt - 1], nums[start] = nums[start], nums[lt - 1]\n",
    "            Qsort(start, lt - 1)\n",
    "            Qsort(gt + 1, end)\n",
    "        \n",
    "        Qsort(0, len(nums) - 1)\n",
    "        return nums[-k]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        \n",
    "        def partition(arr: List[int], low: int, high: int) -> int:\n",
    "            pivot = arr[low]                                        # 选取最左边为pivot\n",
    "\n",
    "            left, right = low, high     # 双指针\n",
    "            while left < right:\n",
    "                \n",
    "                while left<right and arr[right] >= pivot:          # 找到右边第一个<pivot的元素\n",
    "                    right -= 1\n",
    "                arr[left] = arr[right]                             # 并将其移动到left处\n",
    "                \n",
    "                while left<right and arr[left] <= pivot:           # 找到左边第一个>pivot的元素\n",
    "                    left += 1\n",
    "                arr[right] = arr[left]                             # 并将其移动到right处\n",
    "            \n",
    "            arr[left] = pivot           # pivot放置到中间left=right处\n",
    "            return left\n",
    "        \n",
    "        def randomPartition(arr: List[int], low: int, high: int) -> int:\n",
    "            pivot_idx = random.randint(low, high)                   # 随机选择pivot\n",
    "            arr[low], arr[pivot_idx] = arr[pivot_idx], arr[low]     # pivot放置到最左边\n",
    "            return partition(arr, low, high)                        # 调用partition函数\n",
    "\n",
    "        def topKSplit(arr: List[int], low: int, high: int, k: int) -> int:\n",
    "            # mid = partition(arr, low, high)                   # 以mid为分割点【非随机选择pivot】\n",
    "            mid = randomPartition(arr, low, high)               # 以mid为分割点【随机选择pivot】\n",
    "            if mid == k-1:                                      # 第k小元素的下标为k-1\n",
    "                return arr[mid]                                 #【找到即返回】\n",
    "            elif mid < k-1:\n",
    "                return topKSplit(arr, mid+1, high, k)           # 递归对mid右侧元素进行排序\n",
    "            else:\n",
    "                return topKSplit(arr, low, mid-1, k)            # 递归对mid左侧元素进行排序\n",
    "        \n",
    "        n = len(nums)\n",
    "        return topKSplit(nums, 0, n-1, n-k+1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthLargest(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return nums[0]\n",
    "\n",
    "        def sel(left, right):\n",
    "            val = nums[left]\n",
    "            p1 = left + 1\n",
    "            count = 0\n",
    "            while p1 < right and nums[p1] >= val:\n",
    "                if nums[p1] == val: count += 1\n",
    "                p1 += 1\n",
    "            if p1 == right:\n",
    "                p1 -= 1\n",
    "\n",
    "            else:\n",
    "                for p2 in range(p1+1, right):\n",
    "                    if nums[p2] >= val:\n",
    "                        nums[p2], nums[p1] = nums[p1], nums[p2]\n",
    "                        if nums[p2] == val: count += 1\n",
    "                        p1 += 1\n",
    "                p1 -= 1\n",
    "            nums[left], nums[p1] = nums[p1], nums[left]\n",
    "            if p1 - count <= k-1 <= p1:\n",
    "                return val\n",
    "            elif k-1 < p1:\n",
    "                return sel(left, p1)\n",
    "            else:\n",
    "                return sel(p1 + 1, right)\n",
    "\n",
    "        return sel(0, n)\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
